package org.example.myleet.rosalind.root;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private static final int MOD = 1000000;

    private static Map<Integer, Integer> memo = new HashMap<>();

    /**
     * 代码参考：https://github.com/jarecot/Rosalind/blob/master/087_ROOT.py
     * 无根树例子
     *        A - B
     *       /\  /\
     *      C D E F
     * 要转化成有根树，则根可以插入于任意一条变中（AB、AC、AD、BE、BF）
     * 例子中有4个叶子节点，4个叶子节点的无根树有3种状态，每颗无根树都有(2*n - 3)条边，可以生成(2*n - 3)种有根树
     *
     *       A - B
     *      /\
     *     C  D
     *    /\
     *   E  F
     *
     *       A - B
     *      /\
     *     C  D
     *       /\
     *      E  F
     */
    public static void main(String[] args) {
//        int n = 4;
        int n = 935;
        //count unrooted binary trees
        int a = 2 * n - 5;
        int answer = a;
        while (a > 2) {
            answer *= (a = a - 2);
            answer %= MOD;
        }
        //We can transform an unrooted binary tree into a rooted binary tree by inserting a node into any of its 2*n - 3 edges.
        answer = answer * (2 * n - 3) % MOD;
        System.out.println(answer);
    }

    private static int calCombination(int m, int n) {
        Integer result = memo.get(m + n * 1000);
        if (null != result) return result;
        if (m == 1 || m == n - 1) return n;
        if (m == n) return 1;
        result = (calCombination(m - 1, n - 1) + calCombination(m, n - 1)) % MOD;
        memo.put(m + n * 1000, result);
        return result;
    }
}
